1. 题面
  2. 解题思路
  3. Code

题面

解题思路

这是一道用 priority_queue 显然可做的题，然而明明可以反着做，我却一定要正序做……

深深地明白自己的弱小……

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
#define N 200007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
struct node{
    int sco,rew;
    inline void in() {
        sco=read(),rew=read();
    }
    inline bool operator< (const node x) const{
        return sco<x.sco;
    }
}b[N];
int n,m,ans=-1;
LL sum,res,f[N];
priority_queue<int>pl,pr;
int main()
{
    rint i,k,c;
    k=(read()-1)>>1,n=read(),m=read();
    for(i=1;i<=n;i++) b[i].in();
    if(!k) {
        for(i=1;i<=n;i++)
            if(b[i].rew<=m)
            cmax(ans,b[i].sco);
        printf("%d",ans);return 0;
    }sort(b+1,b+n+1);
    for(i=n-k+1;i<=n;i++) res+=b[i].rew,pr.push(b[i].rew);
    for(i=n-k;i>k;--i) {
        f[i]=res;//只不过正序做就不用记录，不知道为什么感觉反着做有点投机取巧……
        if(pr.top()>b[i].rew)
            res=res-pr.top()+b[i].rew,
            pr.pop(),pr.push(b[i].rew);
    }
    for(i=1;i<=k;i++) sum+=b[i].rew,pl.push(b[i].rew);
    for(i=k+1;i<=n-k;i++) {
        if(sum+b[i].rew+f[i]<=m) ans=b[i].sco;
        if(pl.top()>b[i].rew)
            sum=sum-pl.top()+b[i].rew,
            pl.pop(),pl.push(b[i].rew);
    }printf("%d\n",ans);
    return 0;
}

devil.